package com.test.daily.leetcode.y2022.m06.day0609.v01;

import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/9 上午 08:58
 * @version: 1.0
 */
public class Solution {
    public static int minSticks(String[] sticks, String target){
        int N = sticks.length;
        int[][] couts = new int[N][26];
        for(int i = 0; i < 26; i++){
            String stick = sticks[i];
            for(char ch: stick.toCharArray()){
                couts[i][ch - 'a']++;
            }
        }
        int ans = process(couts, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    public static int process(int[][] counts, String target){
        int N = counts.length;
        int[] tcount = new int[26];
        char[] chTarget = target.toCharArray();
        for(char ch: chTarget){
            tcount[ch - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < N; i++){
            int[] count = counts[i];
            if(count[tcount[0] - 'a'] > 0){
                for (int j = 0; j < 26; j++) {
                    int diff = tcount[j] - count[j];
                    if( diff > 0 ){
                        for (int k = 0; k < diff; k++) {
                            builder.append((char)('a' + tcount[j]));
                        }
                    }
                }
            }
            min = Math.min(min, process(counts, builder.toString()));
        }
       
        return min+(min == Integer.MAX_VALUE ? 0: 1);
    }

    public static int minStacks1(String[] sticks, String target){
        int N = sticks.length;
        int[][] counts = new int[N][26];
        for(int i = 0; i < N; i++){
            char[] str = sticks[i].toCharArray();
            for(char ch: str){
                counts[i][ch - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        int ans = process1(counts, target, dp);
        return ans;
    }
    public static int process1(int[][] sticks, String target, HashMap<String, Integer> map){
        if(map.containsKey(target)){
            return map.get(target);
        }
        int[] tcount = new int[26];
        char[] str = target.toCharArray();
        for(char ch: str){
            tcount[ch - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        int N = sticks.length;
        StringBuilder builder = new StringBuilder();
        // int min = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++){
            if(sticks[i][tcount[0]] > 0){
                for(int j = 0; j < 26; j++){
                    int diff = sticks[i][j] - tcount[j];
                    for(int k = 0; k < diff; k++){
                        builder.append((char)('a' + j));
                    }
                }
            }
            min = Math.min(min, process1(sticks, builder.toString(), map));
        }
        int ans = min + (min == Integer.MAX_VALUE ? 0: 1);
        map.put(target, ans);
        return ans;   
    }
}
